const quickSort = function (arr = [], left = 0, right = 0) {
  if (left >= right) return;

  const midIndex = partition(arr, left, right);

  quickSort(arr, left, midIndex - 1);
  quickSort(arr, midIndex + 1, right);

  return arr;
};

function partition(arr, left, right) {
  const midVal = arr[right];
  // 小于枢轴的数下标，左移
  let slow = left - 1;
  for (let j = left; j < right; j++) {
    if (arr[j] <= midVal) {
      slow++;
      [arr[j], arr[slow]] = [arr[slow], arr[j]];
    }
  }
  // 枢轴移到正确位置
  [arr[slow + 1], arr[right]] = [arr[right], arr[slow + 1]];
  return slow + 1;
}
